package com.zhaopin.theswordreferstooffer;

/**
 * @author yin.peide
 * @date 2021-06-25 18:02
 * 面试题37: 两个链表的第一个公共节点
 * 解法1： 蛮力法 O（mn） 就是先定住第一个链表中的一个点，第二个一直往下走，走完了，第一个再下一个，然后第二个再来一遍循环。。。。然后就找到了
 * 解法2： 使用两个辅助栈 ，都完全放到栈里面去，然后弹栈，遇到第一个不同的，前一个就是公共节点
 * 解法3： 首先肯定两个链表长度 一个长 一个短，长的减去短的长度是一个 n值，长的先走n步，然后再一起走，就会同时到达一个相同的节点
 */
public class Offer37 {

    public static void main(String[] args) {

        LinkedNode l1 = new LinkedNode(1);
        LinkedNode l2 = new LinkedNode(2);
        LinkedNode l3 = new LinkedNode(3);
        LinkedNode l4 = new LinkedNode(4);
        LinkedNode l5 = new LinkedNode(5);
        LinkedNode l6 = new LinkedNode(6);
        LinkedNode l7 = new LinkedNode(7);

        l1.next = l2;
        l2.next = l3;
        l3.next = l6;

        l4.next = l5;
        l5.next = l6;

        l6.next = l7;
        LinkedNode linkedNode = getTheSameNode(l4,l1);
        System.out.println(linkedNode.value);


    }

    public static LinkedNode getTheSameNode(LinkedNode linkedNode1, LinkedNode linkedNode2) {

        LinkedNode linkTemp1 = linkedNode1;
        int i = 0;
        while (null != linkTemp1) {
            i++;
            linkTemp1 = linkTemp1.next;
        }

        LinkedNode linkTemp2 = linkedNode2;
        int j = 0;
        while (null != linkTemp2) {
            j++;
            linkTemp2 = linkTemp2.next;
        }

        //拿长得-短的值
        int m = i > j ? i - j : j - i;
        if (i > j) {
            for (int i1 = 0; i1 < m; i1++) {
                linkedNode1 = linkedNode1.next;
            }
        } else {
            for (int i1 = 0; i1 < m; i1++) {
                linkedNode2 = linkedNode2.next;
            }
        }

        //两个剩下的链表一起进行向下走，获取到一致的节点后返回即可
        while (linkedNode1.value != linkedNode2.value) {
            linkedNode1 = linkedNode1.next;
            linkedNode2 = linkedNode2.next;
        }

        return linkedNode1;

    }
}
